package array;

public class leetCode498_findDiagonalOrder {
    public static void main(String[] args) {
        int[][] nums = {{1,2,3},{4,5,6},{7,8,9}};
        leetCode498_findDiagonalOrder a = new leetCode498_findDiagonalOrder();
        a.findDiagonalOrder(nums);
    }
    public int[] findDiagonalOrder(int[][] mat) {
        if(mat == null || mat.length == 0) return new int[]{};
        int n = mat.length;
        int m = mat[0].length;
        int index = 0;
        int[] ans = new int[n * m];
        int k = 0;
        int j = 0;
        // n + m - 2 表示遍历次数
        for (int i = 0; i <= ans.length - 2; i++) {
            if(i % 2 == 0){
                j = i >= n ? n - 1 : i;
                k = i - j;
                while (j >= 0 && k < m){
                    ans[index] = mat[j][k];
                    index++;
                    j--;
                    k++;
                }


            }else{
                k = i >= m ? m - 1 : i;
                j = i - k;
                while (k >= 0 && j < n){
                    ans[index] = mat[j][k];
                    index++;
                    j++;
                    k--;
                }
            }
        }
        return ans;
    }

    public int[] findDiagonalOrder2(int[][] mat) {
        if(mat == null || mat.length == 0) return new int[]{};
        int n = mat.length;
        int m = mat[0].length;
        int[] ans = new int[n * m];
        int j = 0;
        int k = 0;
        int index = 0;
        for (int i = 0; i <= n + m - 2; i++) {
            if(i % 2 == 0){
                j = i >= n ? n - 1 : i;
                k = i - j;
                while (j >= 0 && k < m){
                    ans[index] = mat[j][k];
                    index++;
                    j--;
                    k++;
                }
            }else{
                k = i >= m ? m - 1: i;
                j = i - k;
                while (j < n && k >= 0){
                    ans[index] = mat[j][k];
                    index++;
                    j++;
                    k--;
                }
            }
        }
        return ans;
    }
}
